package hash;

import java.util.ArrayList;
import java.util.HashMap;

public class D230726 {
    // 两数之和
    // 无序数组, 要求返回下标（所以不能改变数组中的内容）
    public int[] twoSum (int[] numbers, int target) {
        int[] res = new int[0];
        //创建哈希表,两元组分别表示值、下标
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        //在哈希表中查找target-numbers[i]
        for(int i = 0; i < numbers.length; i++){
            int temp = target - numbers[i];
            //若是没找到，将此信息计入哈希表
            if(!hash.containsKey(temp))
                hash.put(numbers[i], i);
                //否则返回两个下标+1
            else
                return new int[] {hash.get(temp) + 1, i + 1};
        }
        return res;
    }



    // 数组中出现次数超过一半的数字
    // 方法一：抵消
    public int MoreThanHalfNum_Solution(int[] numbers) {
        int result = 0;// 记录当前较多的数
        int times = 0;// 记录当前较多的数的个数
        for (int i = 0; i < numbers.length; i++) {
            if (times != 0) {
                // 不为0
                if (numbers[i] != result) {
                    // 不相等
                    // 抵消一个
                    times--;
                } else {
                    // 相等
                    times++;
                }
            } else {
                result = numbers[i];
                times = 1;
            }
        }
        return result;
    }
    // 方法二：哈希表记录每个元素出现的次数
    // 方法三：数组排序，返回数组中间的数



    // 数组中只出现一次的两个数字
    // 方法一：哈希统计每个数字的个数，再次遍历数组寻找只出现一次的数字
    public int[] FindNumsAppearOnce (int[] array) {
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
        ArrayList<Integer> res = new ArrayList<Integer>();
        //遍历数组
        for(int i = 0; i < array.length; i++)
            //统计每个数出现的频率
            if(!mp.containsKey(array[i]))
                mp.put(array[i], 1);
            else
                mp.put(array[i], mp.get(array[i]) + 1);
        //再次遍历数组
        for(int i = 0; i < array.length; i++)
            //找到频率为1的两个数
            if(mp.get(array[i]) == 1)
                res.add(array[i]);
        //整理次序
        if(res.get(0) < res.get(1))
            return new int[] {res.get(0), res.get(1)};
        else
            return new int[] {res.get(1), res.get(0)};
    }

    // 方法二：异或运算
    // 相同的数字异或结果为0，0与任何数异或结果为原数字
    // 但是该题有两个出现一次的数
    //
    // 假设这两个数为 a 和 b
    // 首先遍历数组，累计异或，最终得到  a ^ b
    // 那么我们就需要将 a 和 b 分开，分为两组来累计异或，得到 a 和 b
    //
    // 如何分开？才能保证原本的重复数字再同一组
    // 用 2 进制位上的不同来分组，a ^ b 我们找到最低位的 1，因为异或是不同为 1
    public int[] FindNumsAppearOnce2 (int[] array) {
        // 1. 得到 a ^ b
        int temp = 0;
        for (int i = 0; i < array.length; i++) {
            temp ^= array[i];
        }
        // 2. 找到 a 与 b 二进制位上最低位的不同
        int k = 1;
        while ((k & temp) == 0) {
            k <<= 1;
        }
        // 3. 按这个二进制位上的 0 和 1 进行分组累计异或
        int res1 = 0;
        int res2 = 0;
        for (int i = 0; i < array.length; i++) {
            if ((k & temp) == 0) {
                // 为 0 的一组
                res1 ^= array[i];
            } else {
                // 为 1 的一组
                res2 ^= array[i];
            }
        }
        // 4. 调整次序，返回
        if (res1 > res2) {
            return new int[]{res2, res1};
        } else {
            return new int[]{res1, res2};
        }
    }


    // 缺失的第一个正整数
    // 方法一：哈希表记录每个数字，然后从1开始找没有出现的数
    public int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
        //哈希表记录数组中出现的每个数字
        for(int i = 0; i < n; i++)
            mp.put(nums[i], 1);
        int res = 1;
        //从1开始找到哈希表中第一个没有出现的正整数
        while(mp.containsKey(res))
            res++;
        return res;
    }

}
